// Copyright 2016 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/interpreter/bytecode-register-optimizer.h"

namespace v8 {
namespace internal {
    namespace interpreter {

        const uint32_t BytecodeRegisterOptimizer::kInvalidEquivalenceId = kMaxUInt32;

        // A class for tracking the state of a register. This class tracks
        // which equivalence set a register is a member of and also whether a
        // register is materialized in the bytecode stream.
        class BytecodeRegisterOptimizer::RegisterInfo final : public ZoneObject {
        public:
            RegisterInfo(Register reg, uint32_t equivalence_id, bool materialized,
                bool allocated)
                : register_(reg)
                , equivalence_id_(equivalence_id)
                , materialized_(materialized)
                , allocated_(allocated)
                , needs_flush_(false)
                , next_(this)
                , prev_(this)
            {
            }

            void AddToEquivalenceSetOf(RegisterInfo* info);
            void MoveToNewEquivalenceSet(uint32_t equivalence_id, bool materialized);
            bool IsOnlyMemberOfEquivalenceSet() const;
            bool IsOnlyMaterializedMemberOfEquivalenceSet() const;
            bool IsInSameEquivalenceSet(RegisterInfo* info) const;

            // Get a member of the register's equivalence set that is allocated.
            // Returns itself if allocated, and nullptr if there is no unallocated
            // equivalent register.
            RegisterInfo* GetAllocatedEquivalent();

            // Get a member of this register's equivalence set that is
            // materialized. The materialized equivalent will be this register
            // if it is materialized. Returns nullptr if no materialized
            // equivalent exists.
            RegisterInfo* GetMaterializedEquivalent();

            // Get a member of this register's equivalence set that is
            // materialized and not register |reg|. The materialized equivalent
            // will be this register if it is materialized. Returns nullptr if
            // no materialized equivalent exists.
            RegisterInfo* GetMaterializedEquivalentOtherThan(Register reg);

            // Get a member of this register's equivalence set that is intended
            // to be materialized in place of this register (which is currently
            // materialized). The best candidate is deemed to be the register
            // with the lowest index as this permits temporary registers to be
            // removed from the bytecode stream. Returns nullptr if no candidate
            // exists.
            RegisterInfo* GetEquivalentToMaterialize();

            // Marks all temporary registers of the equivalence set as unmaterialized.
            void MarkTemporariesAsUnmaterialized(Register temporary_base);

            // Get an equivalent register. Returns this if none exists.
            RegisterInfo* GetEquivalent();

            Register register_value() const { return register_; }
            bool materialized() const { return materialized_; }
            void set_materialized(bool materialized) { materialized_ = materialized; }
            bool allocated() const { return allocated_; }
            void set_allocated(bool allocated) { allocated_ = allocated; }
            void set_equivalence_id(uint32_t equivalence_id)
            {
                equivalence_id_ = equivalence_id;
            }
            uint32_t equivalence_id() const { return equivalence_id_; }
            // Indicates if a register should be processed when calling Flush().
            bool needs_flush() const { return needs_flush_; }
            void set_needs_flush(bool needs_flush) { needs_flush_ = needs_flush; }

        private:
            Register register_;
            uint32_t equivalence_id_;
            bool materialized_;
            bool allocated_;
            bool needs_flush_;

            // Equivalence set pointers.
            RegisterInfo* next_;
            RegisterInfo* prev_;

            DISALLOW_COPY_AND_ASSIGN(RegisterInfo);
        };

        void BytecodeRegisterOptimizer::RegisterInfo::AddToEquivalenceSetOf(
            RegisterInfo* info)
        {
            DCHECK_NE(kInvalidEquivalenceId, info->equivalence_id());
            // Fix old list
            next_->prev_ = prev_;
            prev_->next_ = next_;
            // Add to new list.
            next_ = info->next_;
            prev_ = info;
            prev_->next_ = this;
            next_->prev_ = this;
            set_equivalence_id(info->equivalence_id());
            set_materialized(false);
        }

        void BytecodeRegisterOptimizer::RegisterInfo::MoveToNewEquivalenceSet(
            uint32_t equivalence_id, bool materialized)
        {
            next_->prev_ = prev_;
            prev_->next_ = next_;
            next_ = prev_ = this;
            equivalence_id_ = equivalence_id;
            materialized_ = materialized;
        }

        bool BytecodeRegisterOptimizer::RegisterInfo::IsOnlyMemberOfEquivalenceSet()
            const
        {
            return this->next_ == this;
        }

        bool BytecodeRegisterOptimizer::RegisterInfo::
            IsOnlyMaterializedMemberOfEquivalenceSet() const
        {
            DCHECK(materialized());

            const RegisterInfo* visitor = this->next_;
            while (visitor != this) {
                if (visitor->materialized()) {
                    return false;
                }
                visitor = visitor->next_;
            }
            return true;
        }

        bool BytecodeRegisterOptimizer::RegisterInfo::IsInSameEquivalenceSet(
            RegisterInfo* info) const
        {
            return equivalence_id() == info->equivalence_id();
        }

        BytecodeRegisterOptimizer::RegisterInfo*
        BytecodeRegisterOptimizer::RegisterInfo::GetAllocatedEquivalent()
        {
            RegisterInfo* visitor = this;
            do {
                if (visitor->allocated()) {
                    return visitor;
                }
                visitor = visitor->next_;
            } while (visitor != this);

            return nullptr;
        }

        BytecodeRegisterOptimizer::RegisterInfo*
        BytecodeRegisterOptimizer::RegisterInfo::GetMaterializedEquivalent()
        {
            RegisterInfo* visitor = this;
            do {
                if (visitor->materialized()) {
                    return visitor;
                }
                visitor = visitor->next_;
            } while (visitor != this);

            return nullptr;
        }

        BytecodeRegisterOptimizer::RegisterInfo*
        BytecodeRegisterOptimizer::RegisterInfo::GetMaterializedEquivalentOtherThan(
            Register reg)
        {
            RegisterInfo* visitor = this;
            do {
                if (visitor->materialized() && visitor->register_value() != reg) {
                    return visitor;
                }
                visitor = visitor->next_;
            } while (visitor != this);

            return nullptr;
        }

        BytecodeRegisterOptimizer::RegisterInfo*
        BytecodeRegisterOptimizer::RegisterInfo::GetEquivalentToMaterialize()
        {
            DCHECK(this->materialized());
            RegisterInfo* visitor = this->next_;
            RegisterInfo* best_info = nullptr;
            while (visitor != this) {
                if (visitor->materialized()) {
                    return nullptr;
                }
                if (visitor->allocated() && (best_info == nullptr || visitor->register_value() < best_info->register_value())) {
                    best_info = visitor;
                }
                visitor = visitor->next_;
            }
            return best_info;
        }

        void BytecodeRegisterOptimizer::RegisterInfo::MarkTemporariesAsUnmaterialized(
            Register temporary_base)
        {
            DCHECK(this->register_value() < temporary_base);
            DCHECK(this->materialized());
            RegisterInfo* visitor = this->next_;
            while (visitor != this) {
                if (visitor->register_value() >= temporary_base) {
                    visitor->set_materialized(false);
                }
                visitor = visitor->next_;
            }
        }

        BytecodeRegisterOptimizer::RegisterInfo*
        BytecodeRegisterOptimizer::RegisterInfo::GetEquivalent()
        {
            return next_;
        }

        BytecodeRegisterOptimizer::BytecodeRegisterOptimizer(
            Zone* zone, BytecodeRegisterAllocator* register_allocator,
            int fixed_registers_count, int parameter_count,
            BytecodeWriter* bytecode_writer)
            : accumulator_(Register::virtual_accumulator())
            , temporary_base_(fixed_registers_count)
            , max_register_index_(fixed_registers_count - 1)
            , register_info_table_(zone)
            , registers_needing_flushed_(zone)
            , equivalence_id_(0)
            , bytecode_writer_(bytecode_writer)
            , flush_required_(false)
            , zone_(zone)
        {
            register_allocator->set_observer(this);

            // Calculate offset so register index values can be mapped into
            // a vector of register metadata.
            // There is at least one parameter, which is the JS receiver.
            DCHECK_NE(parameter_count, 0);
            register_info_table_offset_ = -Register::FromParameterIndex(0, parameter_count).index();

            // Initialize register map for parameters, locals, and the
            // accumulator.
            register_info_table_.resize(register_info_table_offset_ + static_cast<size_t>(temporary_base_.index()));
            for (size_t i = 0; i < register_info_table_.size(); ++i) {
                register_info_table_[i] = new (zone) RegisterInfo(
                    RegisterFromRegisterInfoTableIndex(i), NextEquivalenceId(), true, true);
                DCHECK_EQ(register_info_table_[i]->register_value().index(),
                    RegisterFromRegisterInfoTableIndex(i).index());
            }
            accumulator_info_ = GetRegisterInfo(accumulator_);
            DCHECK(accumulator_info_->register_value() == accumulator_);
        }

        void BytecodeRegisterOptimizer::PushToRegistersNeedingFlush(RegisterInfo* reg)
        {
            if (!reg->needs_flush()) {
                reg->set_needs_flush(true);
                registers_needing_flushed_.push_back(reg);
            }
        }

        bool BytecodeRegisterOptimizer::EnsureAllRegistersAreFlushed() const
        {
            for (RegisterInfo* reg_info : register_info_table_) {
                if (reg_info->needs_flush()) {
                    return false;
                } else if (!reg_info->IsOnlyMemberOfEquivalenceSet()) {
                    return false;
                } else if (reg_info->allocated() && !reg_info->materialized()) {
                    return false;
                }
            }
            return true;
        }

        void BytecodeRegisterOptimizer::Flush()
        {
            if (!flush_required_) {
                return;
            }

            // Materialize all live registers and break equivalences.
            for (RegisterInfo* reg_info : registers_needing_flushed_) {
                if (!reg_info->needs_flush())
                    continue;
                reg_info->set_needs_flush(false);

                RegisterInfo* materialized = reg_info->materialized()
                    ? reg_info
                    : reg_info->GetMaterializedEquivalent();

                if (materialized != nullptr) {
                    // Walk equivalents of materialized registers, materializing
                    // each equivalent register as necessary and placing in their
                    // own equivalence set.
                    RegisterInfo* equivalent;
                    while ((equivalent = materialized->GetEquivalent()) != materialized) {
                        if (equivalent->allocated() && !equivalent->materialized()) {
                            OutputRegisterTransfer(materialized, equivalent);
                        }
                        equivalent->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
                        equivalent->set_needs_flush(false);
                    }
                } else {
                    // Equivalernce class containing only unallocated registers.
                    DCHECK_NULL(reg_info->GetAllocatedEquivalent());
                    reg_info->MoveToNewEquivalenceSet(NextEquivalenceId(), false);
                }
            }

            registers_needing_flushed_.clear();
            DCHECK(EnsureAllRegistersAreFlushed());

            flush_required_ = false;
        }

        void BytecodeRegisterOptimizer::OutputRegisterTransfer(
            RegisterInfo* input_info, RegisterInfo* output_info)
        {
            Register input = input_info->register_value();
            Register output = output_info->register_value();
            DCHECK_NE(input.index(), output.index());

            if (input == accumulator_) {
                bytecode_writer_->EmitStar(output);
            } else if (output == accumulator_) {
                bytecode_writer_->EmitLdar(input);
            } else {
                bytecode_writer_->EmitMov(input, output);
            }
            if (output != accumulator_) {
                max_register_index_ = std::max(max_register_index_, output.index());
            }
            output_info->set_materialized(true);
        }

        void BytecodeRegisterOptimizer::CreateMaterializedEquivalent(
            RegisterInfo* info)
        {
            DCHECK(info->materialized());
            RegisterInfo* unmaterialized = info->GetEquivalentToMaterialize();
            if (unmaterialized) {
                OutputRegisterTransfer(info, unmaterialized);
            }
        }

        BytecodeRegisterOptimizer::RegisterInfo*
        BytecodeRegisterOptimizer::GetMaterializedEquivalent(RegisterInfo* info)
        {
            return info->materialized() ? info : info->GetMaterializedEquivalent();
        }

        BytecodeRegisterOptimizer::RegisterInfo*
        BytecodeRegisterOptimizer::GetMaterializedEquivalentNotAccumulator(
            RegisterInfo* info)
        {
            if (info->materialized()) {
                return info;
            }

            RegisterInfo* result = info->GetMaterializedEquivalentOtherThan(accumulator_);
            if (result == nullptr) {
                Materialize(info);
                result = info;
            }
            DCHECK(result->register_value() != accumulator_);
            return result;
        }

        void BytecodeRegisterOptimizer::Materialize(RegisterInfo* info)
        {
            if (!info->materialized()) {
                RegisterInfo* materialized = info->GetMaterializedEquivalent();
                DCHECK_NOT_NULL(materialized);
                OutputRegisterTransfer(materialized, info);
            }
        }

        void BytecodeRegisterOptimizer::AddToEquivalenceSet(
            RegisterInfo* set_member, RegisterInfo* non_set_member)
        {
            // Equivalence class is now of size >= 2, so we make sure it will be flushed.
            PushToRegistersNeedingFlush(non_set_member);
            non_set_member->AddToEquivalenceSetOf(set_member);
            // Flushing is only required when two or more registers are placed
            // in the same equivalence set.
            flush_required_ = true;
        }

        void BytecodeRegisterOptimizer::RegisterTransfer(RegisterInfo* input_info,
            RegisterInfo* output_info)
        {
            bool output_is_observable = RegisterIsObservable(output_info->register_value());
            bool in_same_equivalence_set = output_info->IsInSameEquivalenceSet(input_info);
            if (in_same_equivalence_set && (!output_is_observable || output_info->materialized())) {
                return; // Nothing more to do.
            }

            // Materialize an alternate in the equivalence set that
            // |output_info| is leaving.
            if (output_info->materialized()) {
                CreateMaterializedEquivalent(output_info);
            }

            // Add |output_info| to new equivalence set.
            if (!in_same_equivalence_set) {
                AddToEquivalenceSet(input_info, output_info);
            }

            if (output_is_observable) {
                // Force store to be emitted when register is observable.
                output_info->set_materialized(false);
                RegisterInfo* materialized_info = input_info->GetMaterializedEquivalent();
                OutputRegisterTransfer(materialized_info, output_info);
            }

            bool input_is_observable = RegisterIsObservable(input_info->register_value());
            if (input_is_observable) {
                // If input is observable by the debugger, mark all other temporaries
                // registers as unmaterialized so that this register is used in preference.
                input_info->MarkTemporariesAsUnmaterialized(temporary_base_);
            }
        }

        void BytecodeRegisterOptimizer::PrepareOutputRegister(Register reg)
        {
            RegisterInfo* reg_info = GetRegisterInfo(reg);
            if (reg_info->materialized()) {
                CreateMaterializedEquivalent(reg_info);
            }
            reg_info->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
            max_register_index_ = std::max(max_register_index_, reg_info->register_value().index());
        }

        void BytecodeRegisterOptimizer::PrepareOutputRegisterList(
            RegisterList reg_list)
        {
            int start_index = reg_list.first_register().index();
            for (int i = 0; i < reg_list.register_count(); ++i) {
                Register current(start_index + i);
                PrepareOutputRegister(current);
            }
        }

        Register BytecodeRegisterOptimizer::GetInputRegister(Register reg)
        {
            RegisterInfo* reg_info = GetRegisterInfo(reg);
            if (reg_info->materialized()) {
                return reg;
            } else {
                RegisterInfo* equivalent_info = GetMaterializedEquivalentNotAccumulator(reg_info);
                return equivalent_info->register_value();
            }
        }

        RegisterList BytecodeRegisterOptimizer::GetInputRegisterList(
            RegisterList reg_list)
        {
            if (reg_list.register_count() == 1) {
                // If there is only a single register, treat it as a normal input register.
                Register reg(GetInputRegister(reg_list.first_register()));
                return RegisterList(reg);
            } else {
                int start_index = reg_list.first_register().index();
                for (int i = 0; i < reg_list.register_count(); ++i) {
                    Register current(start_index + i);
                    RegisterInfo* input_info = GetRegisterInfo(current);
                    Materialize(input_info);
                }
                return reg_list;
            }
        }

        void BytecodeRegisterOptimizer::GrowRegisterMap(Register reg)
        {
            DCHECK(RegisterIsTemporary(reg));
            size_t index = GetRegisterInfoTableIndex(reg);
            if (index >= register_info_table_.size()) {
                size_t new_size = index + 1;
                size_t old_size = register_info_table_.size();
                register_info_table_.resize(new_size);
                for (size_t i = old_size; i < new_size; ++i) {
                    register_info_table_[i] = new (zone()) RegisterInfo(RegisterFromRegisterInfoTableIndex(i),
                        NextEquivalenceId(), true, false);
                }
            }
        }

        void BytecodeRegisterOptimizer::AllocateRegister(RegisterInfo* info)
        {
            info->set_allocated(true);
            if (!info->materialized()) {
                info->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
            }
        }

        void BytecodeRegisterOptimizer::RegisterAllocateEvent(Register reg)
        {
            AllocateRegister(GetOrCreateRegisterInfo(reg));
        }

        void BytecodeRegisterOptimizer::RegisterListAllocateEvent(
            RegisterList reg_list)
        {
            if (reg_list.register_count() != 0) {
                int first_index = reg_list.first_register().index();
                GrowRegisterMap(Register(first_index + reg_list.register_count() - 1));
                for (int i = 0; i < reg_list.register_count(); i++) {
                    AllocateRegister(GetRegisterInfo(Register(first_index + i)));
                }
            }
        }

        void BytecodeRegisterOptimizer::RegisterListFreeEvent(RegisterList reg_list)
        {
            int first_index = reg_list.first_register().index();
            for (int i = 0; i < reg_list.register_count(); i++) {
                GetRegisterInfo(Register(first_index + i))->set_allocated(false);
            }
        }

    } // namespace interpreter
} // namespace internal
} // namespace v8
